Click an operation on the right, or select a node in the tree.

Min, Max, Successor, Predecessor

These operations leverage the BST property to find elements efficiently.

Tree-wide Operations

Node-specific Operations

First, click a node on the tree to select it.

Select an operation to see a detailed explanation of its algorithm.

Algorithm: Find Minimum

The BST property guarantees that the minimum value is always the leftmost node in the tree.

  1. Start at the root node.
  2. Repeatedly follow the left child pointer.
  3. The last node reached (which has no left child) is the minimum.

Algorithm: Find Maximum

Symmetrically, the maximum value is always the rightmost node in the tree.

  1. Start at the root node.
  2. Repeatedly follow the right child pointer.
  3. The last node reached (which has no right child) is the maximum.

Algorithm: Find Successor

The successor of a node \(x\) is the node with the smallest key greater than \(x\)'s key. There are two cases:

  1. If node \(x\) has a right subtree: The successor is the minimum value in that right subtree.
  2. If node \(x\) has no right subtree: The successor is the lowest ancestor of \(x\) whose left child is also an ancestor of \(x\).

Algorithm: Find Predecessor

The predecessor of a node \(x\) is the node with the largest key smaller than \(x\)'s key. This is symmetric to finding the successor:

  1. If node \(x\) has a left subtree: The predecessor is the maximum value in that left subtree.
  2. If node \(x\) has no left subtree: The predecessor is the lowest ancestor of \(x\) whose right child is also an ancestor of \(x\).